package com.cty.C_SortAlgorithms.C_InsertSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/17 10:42
 * @Description: 插入排序  基于数组实现
 * @version: 1.0
 */
public class InsertSort {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public InsertSort(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 在数组末尾插入数据  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }


    /**
     * 插入排序
     *      平均时间复杂度：  O(N^2)    数据随机分布    s = 比较次数 + 移动次数 + 移动到temp = N*(N-1)/4 + N*(N-1)/4 + N-1    算法从1到N-1共执行N轮；每轮首先将当前数据移动到temp，之后每次比较伴随一次移动；平均来说在中途遇到比较中止条件。
     *      最好情况：        O(N)      数据顺序分布    s = 比较次数 + 移动次数 + 移动到temp = N-1 + N-1 + N-1    算法从1到N-1共执行N轮；每轮首先将当前数据移动到temp，之后比较一次和移动一次；也就是第一次比较就遇到中止条件。
     *      最坏情况：       O(N^2)     数据逆序分布    s = 比较次数 + 移动次数 + 移动到temp = N*(N-1)/2 + N*(N-1)/2 + N-1    算法从1到N-1共执行N轮；每轮首先将当前数据移动到temp，之后每次比较伴随一次移动，直到数组头部；也就是比较完所有数据才中止。
     *      空间复杂度：      O(1)      不需要额外空间辅助
     *      排序方式：                  内部排序
     *      稳定性：                    稳定
     */
    public void insertSort(){
        int in, out;
        for(out=1; out<nItems; out++){
            DataItem temp = array[out].getItem();  // 完整的复制体
            in = out;
            while(in>0 && array[in-1].getKey()>temp.getKey()){  // > 保证稳定性
                array[in].setItem(array[in-1].getItem());
                in--;
            }
            array[in].setItem(temp);
        }  // end for
    }  // end insertSort()







    // 练习 插入排序






}  // end InsertSort{}
